package leetcode_top;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import org.junit.*;

import utils.BracketUtils;
public class Ex210 {

    class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            if (numCourses <= 0) {
                return new int[0];
            }
    
            Set<Integer>[] adj = new HashSet[numCourses];
            for (int i = 0; i < numCourses; i++) {
                adj[i] = new HashSet<>();
            }
    
            // [1,0] 0 -> 1
            int[] inDegree = new int[numCourses];
            for (int[] p : prerequisites) {
                adj[p[1]].add(p[0]);
                inDegree[p[0]]++;
            }
    
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) {
                if (inDegree[i] == 0) {
                    queue.offer(i);
                }
            }
    
            int[] res = new int[numCourses];
            // 当前结果集列表里的元素个数，正好可以作为下标
            int count = 0;
    
            while (!queue.isEmpty()) {
                // 当前入度为 0 的结点
                Integer head = queue.poll();
                res[count] = head;
                count++;
    
                Set<Integer> successors = adj[head];
                for (Integer nextCourse : successors) {
                    inDegree[nextCourse]--;
                    // 马上检测该结点的入度是否为 0，如果为 0，马上加入队列
                    if (inDegree[nextCourse] == 0) {
                        queue.offer(nextCourse);
                    }
                }
            }
            
            // 如果结果集中的数量不等于结点的数量，就不能完成课程任务，这一点是拓扑排序的结论
            if (count == numCourses) {
                return res;
            }
            return new int[0];
        }
    }
    
    class Solution1 {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<Integer> res = new ArrayList<>();
            Set<Integer> finished = Stream.iterate(0, i -> i + 1).limit(numCourses).collect(Collectors.toSet());
            Set<Integer> unfinished = new HashSet<>();
            Map<Integer, List<Integer>> map = new HashMap<>();
            int[] f = new int[numCourses];
            for (int j = 0; j < prerequisites.length; j++) {
                f[prerequisites[j][0]]++;
                finished.remove(prerequisites[j][0]);
                unfinished.add(prerequisites[j][0]);
                if (map.containsKey(prerequisites[j][1])) {
                    map.get(prerequisites[j][1]).add(prerequisites[j][0]);
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(prerequisites[j][0]);
                    map.put(prerequisites[j][1], list);
                }
            }

            res.addAll(finished);
            int t, cur;
            while (!unfinished.isEmpty()) {
                if (finished.isEmpty()) return new int[0];
                Iterator<Integer> iterator = finished.iterator();
                Set<Integer> set = new HashSet<>();
                while (iterator.hasNext()) {
                    cur = iterator.next();
                    List<Integer> list = map.get(cur);
                    iterator.remove();
                    if (list == null) {
                        continue;
                    }
                    for (int i = 0; i < list.size(); i++) {
                        t = list.get(i);
                        f[t]--;
                        if (f[t] == 0) {
                            unfinished.remove(t);
                            res.add(t);
                            set.add(t);
                        }
                    }
                }    
                finished = set;
            }
            return res.stream().mapToInt(Integer::valueOf).toArray();
        }
    }

    class Solution2 {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            Set<Integer> finished = Stream.iterate(0, i -> i + 1).limit(10).collect(Collectors.toSet());
            Set<Integer> unfinished = new HashSet<>();

            Map<Integer, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < prerequisites.length; i++) {
                if (map.containsKey(prerequisites[i][0])) {
                    map.get(prerequisites[i][0]).add(prerequisites[i][1]);
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(prerequisites[i][1]);
                    map.put(prerequisites[i][0], list);
                }
                finished.remove(prerequisites[i][0]);
                unfinished.add(prerequisites[i][0]);
            }
            List<Integer> res = new ArrayList<>(finished);
            dfs(map, unfinished, res);
            return res.stream().mapToInt(Integer::valueOf).toArray();
        }

        public int get(Map<Integer, List<Integer>> map, int cur, Set<Integer> set) {
            if (map.get(cur) == null) {
                return cur;
            }
            // List<Integer> list = map.get(cur);
            // for (int i = 0; i < list.size(); i++) {
            //     if (set.contains(list.get(i))) return -1;
            //     set.add(list.get(i));
            //     return get(map, list.get(i), set);
            // }
            return -1;
        }

        private void dfs(Map<Integer, List<Integer>> map, Set<Integer> unfinished, List<Integer> res) {
            if (unfinished.isEmpty()) return;
            for (int s: unfinished) {
                if (map.containsKey(s)) {
                    List<Integer> list = map.get(s);
                    for (int i = 0; i < list.size(); i++) {
                        
                    }
                }
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] f = BracketUtils.to2DArray("[[1,0],[2,0],[3,1],[3,2]]");
        // f = BracketUtils.to2DArray("[[1,0]]");
        int[] res = s.findOrder(4, f);        
        // res = s.findOrder(3, f);
        System.out.println(Arrays.toString(res));
        System.out.println(IntStream.of(f[0]).distinct().boxed().collect(Collectors.toSet()));
    }


    @Test
    public void test1() {
        int[] nums = new int[]{1,2,3};
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            int cur =iterator.next();
            System.out.println(cur);
            iterator.remove();
            // set.add(1);
            set.remove(3);
        }
        System.out.println(iterator.hasNext());
    }
}
